//选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
//按增量序列个数k，对序列进行k 趟排序；
//每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。
//仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

//它与插入排序的不同之处在于，它会优先比较距离较远的元素

// function shellSort(arr) {
//     let len = arr.length;
//     let proIndex;
//     let current;
//     for (let gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
//         for (let i = gap; i < len; i++) {
//             proIndex = i;
//             current = arr[i];
//             while (proIndex - gap >= 0 && current < arr[proIndex - gap]) {
//                 arr[proIndex] = arr[proIndex - gap];
//                 proIndex = proIndex - gap;
//             }
//             arr[proIndex] = current;
//         }
//     }
//     return arr
// }



function shellSort(arr) {
    let len = arr.length;
    let pre;
    let curr;
    for (let gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
        for (let i = gap; i < len; i++) {
            pre = i;
            curr = arr[i];
            while (pre >= 0 && arr[pre - gap] > curr) {
                arr[pre] = arr[pre - gap];
                pre = pre - gap;
            }
            arr[pre] = curr
        }
    }
    return arr;
}

var arr = [3, 5, 7, 1, 4, 2, 12, 78, 25, 0, 9];

console.log(shellSort(arr));

//时间复杂度：最好的情况原本就是有序O(n) 最坏的情况 O（n的平方） 平均O（n的1.3次方）
//空间复杂度：O（1）